﻿#pragma once
#include "stdafx.h"

/*
盛最多水的容器 中等

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。


图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

 

 示例：

 输入：[1,8,6,2,5,4,8,3,7]
 输出：49

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/container-with-most-water
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 解题思路，从最开始看到题目，其实就如同找到最大值一样，面积不就是底×高，高为min（x,y）.t为两个下标距离
 从传统遍历的话，设置I，j，这样的话时间复杂度为O(n^2).但是找到最大值的例子可是O（n），
 于是便想t在最大的时候是确定的，数组确定下来后。不妨左右开始记录下标，向中间进攻。

 于是这就是双指针法，专门用来确定边界的一些问题。

 
  当 x <= y  ,我们移动y 为y1: 由min(x,y) == x; t移动一下，为t1 < t;
  当 y1 <= y,  min(x, y1) <= min(x, y)
  当 y1 > y   min(x,y1) == x == min(x,y)
  面积 s = min(x,y1)*t1  <= min(x,y)*t1 < min(x,y)*t;  
  所以移动大的数据，得到的结果比开始的小，所以不能移动大的，

  当移动小的，x <= y  我们移动小的x 为x1,由min(x,y) == x  t移动一下，为t1 < t;
  当 x1 <= x   min(x1, y) <= min(x, y)  结果当然比这个小了，
  只有 x1 > x的时候 面积才不缺定，才有可能比较大，这个不就是记录最大值问题，

  遍历下来也就是线性的 O(n);
  
*/

int maxArea(vector<int>& height) {
	int l = 0, r = height.size() - 1;
	int ans = 0;
	while (l < r) {
		int area = min(height[l], height[r]) * (r - l);
		ans = max(ans, area);
		if (height[l] <= height[r]) {
			++l;
		}
		else {
			--r;
		}
	}
	return ans;
}

void testmaxArea()
{
	vector<int> height = {1,8,6,2,5,4,8,3,7};

	int data = maxArea(height);

	cout << "the height is " << data << endl;
}

/*
结果：
the height is 49
*/